#include<iostream>
using namespace std;
#include<fstream>

/*
 * int n:  number of known data points
 * double x: the interpolation/extrapolation point x coordinate
 */
double LagPoly( int n, double * xdata, double * ydata, double x ){

	double y=0, z;
	for(int i=0;i<n;i++){
		z = 1;
		for(int k=0;k<n;k++){
			if( k != i ) z *= (x - xdata[k] )/ ( xdata[i] - xdata[k] );
		}
		y += ydata[i] * z;
	}
	return y;
}

int main(){

	int n;
	cout<<" number of known data points n = "; cin>>n;
	double x;
	cout<<" interpolation/extrapolation position x = "; cin>>x;
	double * xdata = new double [n];
	double * ydata = new double [n];

	ifstream fp("PolyInput.txt");
	for(int i=0;i<n;i++)
		fp >> xdata[i] >> ydata[i];

	cout<<" y(x) = "<< LagPoly( n, xdata, ydata, x )<<endl;

	fp.close();

	ofstream out("PolyCurve.txt");
	for(double x = 0.5; x <=4.5; x += 0.01 ){
		out<< x <<"\t" << LagPoly( n, xdata, ydata, x )<<endl;
	}
	out.close();

	return 0;
}
